package priority;

public class MaxPriorityQueue<T extends Comparable<T>> {
    private T[] items;
    private int N;

    MaxPriorityQueue(int capacity) {
        items = (T[]) new Comparable[capacity + 1];
        N = 0;
    }


    private boolean less(int i, int j) {
        return items[i].compareTo(items[j]) < 0;

    }

    private void exchange(int i, int j) {
        T temp = items[i];
        items[i] = items[j];
        items[j] = temp;
    }

    public T delMax() {
        T max = items[1];
        // 交换 1 N
        exchange(1, N);
        // 删除N
        items[N] = null;
        N--;
        // 下沉1
        sink(1);
        return max;
    }

    private void sink(int k) {
        while (k * 2 <= N) {
            int max;
            if (k * 2 + 1 <= N) {
                // 有右
                if (less(k * 2, k * 2 + 1)) {
                    // 右大
                    max = k * 2 + 1;
                } else {
                    max = k * 2;
                }
            } else {
                // 只有左
                max = k * 2;
            }
            if (less(max, k)) {
                // 当前大
                break;
            }
            // 当前小
            exchange(max, k);
            k = max;
        }
    }

    public void insert(T t) {
        items[++N] = t;
        swim(N);
    }

    private void swim(int k) {
        while (k > 1) {
            if (less(k / 2, k)) {
                exchange(k / 2, k);
            }
            k = k / 2;
        }
    }

    public int size() {
        return N;
    }

    public boolean isEmpty() {
        return N == 0;
    }

    public static void main(String[] args) {

        String[] arr = {"S", "O", "R", "T", "E", "X", "A", "M", "P", "L", "E"};
        MaxPriorityQueue<String> maxpq = new MaxPriorityQueue<>(20);
        for (String s : arr) {
            maxpq.insert(s);
        }
        System.out.println(maxpq.size());
        String del;
        while (!maxpq.isEmpty()) {
            del = maxpq.delMax();
            System.out.print(del + ",");
        }
    }

}
